package github.lyf.middle;

import java.util.*;

/**
 * @author yunfei.li
 * @date 2021/10/22 15:42
 */
public class MajorityElement {
    /**
     * 给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
     * <p>
     * 示例 1：
     * <p>
     * 输入：[3,2,3]
     * 输出：[3]
     * 示例 2：
     * <p>
     * 输入：nums = [1]
     * 输出：[1]
     * 示例 3：
     * <p>
     * 输入：[1,1,1,3,3,2,2,2]
     * 输出：[1,2]
     *  
     * <p>
     * 提示：
     * <p>
     * 1 <= nums.length <= 5 * 104
     * -109 <= nums[i] <= 109
     *  
     * <p>
     * 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
     *
     * @param nums
     * @return
     */
    public static List<Integer> majorityElement(int[] nums) {
        int length = nums.length;
        int count = length / 3;
        Set<Integer> res = new HashSet<>();
        if (length == 1) {
            res.add(nums[0]);
            return new ArrayList<>(res);
        }
        if (length == 2) {
            res.add(nums[0]);
            res.add(nums[1]);
            return new ArrayList<>(res);
        }
        Arrays.sort(nums);
        int i = 0;
        int j = 0;
        while (j < length) {
            if (nums[i] == nums[j]) {
                j++;
                if (j == length) {
                    if (j - i > count) {
                        res.add(nums[i]);
                    }
                    break;
                }
            } else {
                if (j - i > count) {
                    res.add(nums[i]);
                }
                i = j;
                j++;
            }

        }
        return new ArrayList<>(res);
    }

    /**
     * 摩尔投票法
     * @param nums
     * @return
     */
    public static List<Integer> majorityElement1(int[] nums) {
        // 创建返回值
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        // 初始化两个候选人candidate，和他们的计票
        int cand1 = nums[0], count1 = 0;
        int cand2 = nums[0], count2 = 0;

        // 摩尔投票法，分为两个阶段：配对阶段和计数阶段
        // 配对阶段
        for (int num : nums) {
            // 投票
            if (cand1 == num) {
                count1++;
                continue;
            }
            if (cand2 == num) {
                count2++;
                continue;
            }

            // 第1个候选人配对
            if (count1 == 0) {
                cand1 = num;
                count1++;
                continue;
            }
            // 第2个候选人配对
            if (count2 == 0) {
                cand2 = num;
                count2++;
                continue;
            }

            count1--;
            count2--;
        }

        // 计数阶段
        // 找到了两个候选人之后，需要确定票数是否满足大于 N/3
        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (cand1 == num) count1++;
            else if (cand2 == num) count2++;
        }

        if (count1 > nums.length / 3) res.add(cand1);
        if (count2 > nums.length / 3) res.add(cand2);

        return res;
    }

    public static void main(String[] args) {
        majorityElement1(new int[]{1, 2});
    }
}
